package offer.linkedList;

/**
 * @author DengYuan2
 * @create 2021-02-23 19:41
 */
public class n_25 {
    public static void main(String[] args) {
        n_25 n = new n_25();
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(5);
        ListNode n4 = new ListNode(2);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        n1.next = n2;
        n2.next = n3;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        ListNode merge = n.Merge(n1, n4);
        System.out.println(merge);
    }

    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode dumb = new ListNode(-1);
        ListNode cur = dumb;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        }
        if (list2 != null) {
            cur.next = list2;
        }
        return dumb.next;

    }

    /**
     * 大神-递归
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode Merge2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge2(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge2(list2.next, list1);
            return list2;
        }

    }
}